package com.elloe.实现二叉树的Node节点.非递归的后序遍历;

import com.elloe.实现二叉树的Node节点.Node的Java实现.Node;

import java.util.Stack;

/**
 * @author ElloeStudy(Sifa Zhang)
 * @create 2022-04-09 19:27
 * To: 真常应物，真常得性，常清常静，常清静矣
 */
public class TraversalAfterByLoop {
    public void traversalAfterByLoop(Node node){
        // 存放还没有完成操作的节点，临时储存
        Stack<Node> stack = new Stack<>();
        Node present = node; // 当前的操作节点
        Node prev = node;  // 先前的根节点（一个标志flag）

        while (present != null || !stack.isEmpty()){
            // 当前的节点不为null 且 栈不为空

            while(present != null){
                // 如果当前的节点不为空

                stack.push(present); // 将当前这个节点临时存储
                present = present.getLeft(); // 遍历获取其左节点
            }

            if (!stack.isEmpty()){
                // 拿出栈顶的值，并没有进行删除
                Node temp = stack.peek().getRight(); // 获取栈顶节点的右节点

                // 节点没有右节点或者到达根节点【考虑到了最后一种情况】
                if (temp == null || temp == prev){
                    present = stack.pop();
                    // 获取根节点
                    System.out.print(present.getValue() + " ");

                    prev = present;   // 将当前的节点作为 根节点的标志（flag）
                    present = null;  // 将当前节点 设为空
                }else{
                    // 节点有右节点 或者 没有到达根节点
                    present = temp; // 将这个右节点设置为当前节点
                }
            }
        }
    }
}
